Search Results

Documents authored by Vanderpooten, Daniel


Document
Optimizing over the Efficient Set of a Multi-Objective Discrete Optimization Problem

Authors: Satya Tamby and Daniel Vanderpooten

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)


Abstract
Optimizing over the efficient set of a discrete multi-objective problem is a challenging issue. The main reason is that, unlike when optimizing over the feasible set, the efficient set is implicitly characterized. Therefore, methods designed for this purpose iteratively generate efficient solutions by solving appropriate single-objective problems. However, the number of efficient solutions can be quite large and the problems to be solved can be difficult practically. Thus, the challenge is both to minimize the number of iterations and to reduce the difficulty of the problems to be solved at each iteration. In this paper, a new enumeration scheme is proposed. By introducing some constraints and optimizing over projections of the search region, potentially large parts of the search space can be discarded, drastically reducing the number of iterations. Moreover, the single-objective programs to be solved can be guaranteed to be feasible, and a starting solution can be provided allowing warm start resolutions. This results in a fast algorithm that is simple to implement. Experimental computations on two standard multi-objective instance families show that our approach seems to perform significantly faster than the state of the art algorithm.

Cite as

Satya Tamby and Daniel Vanderpooten. Optimizing over the Efficient Set of a Multi-Objective Discrete Optimization Problem. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 9:1-9:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{tamby_et_al:LIPIcs.SEA.2023.9,
  author =	{Tamby, Satya and Vanderpooten, Daniel},
  title =	{{Optimizing over the Efficient Set of a Multi-Objective Discrete Optimization Problem}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{9:1--9:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-279-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{265},
  editor =	{Georgiadis, Loukas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.9},
  URN =		{urn:nbn:de:0030-drops-183599},
  doi =		{10.4230/LIPIcs.SEA.2023.9},
  annote =	{Keywords: discrete optimization, multi-objective optimization, non-dominated set, efficient set}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail